package xkp.lesson3;

public class 普通查找 {
	public static void main(String[] args) {
		int[] arr = {1,3,6,2,8,4,9,10,22,45,67};
		quickSort(arr, 0, arr.length-1);
		printArr(arr);
		int index = searchIndex(arr, 10);
		//System.out.println(index);
		//如果采取高级方式
		//1、先对数组进行排序
		//2、对排序后数组使用算法查找(二分查找)
		//二分查找如果查找10次可以查找找到1024个元素的数组中的值。
		
	}
	
	/*
	 * 方法的格式
	 * 访问修饰符    返回值类型    方法名称(形参列表，可以为空){   方法体，可以有返回值              }
	 * {}表示代码块,;表示一条语句的结束
	 */
	public static void printArr(int[] arr) {
		{
			//我是代码块
			//
		}
		for(int i = 0; i < arr.length; i++) {
			System.out.print(arr[i]+"\t");
		}
		System.out.println();
	}
	
	
    public static void quickSort(int[] arr,int low,int high){
        int i,j,temp,t;
        if(low>=high){
            return;
        }
        i=low;
        j=high;
        //temp就是基准位
        temp = arr[low];
 
        while (i<j) {
            //先看右边，依次往左递减
            while (temp<=arr[j]&&i<j) {
                j--;
            }
            //再看左边，依次往右递增
            while (temp>=arr[i]&&i<j) {
                i++;
            }
            //如果满足条件则交换
            if (i<j) {
                t = arr[j];
                arr[j] = arr[i];
                arr[i] = t;
            }
 
        }
        //最后将基准为与i和j相等位置的数字交换
         arr[low] = arr[i];
         arr[i] = temp;
        //递归调用左半数组
        quickSort(arr, low, j-1);
        //递归调用右半数组
        quickSort(arr, j+1, high);
    }
 
	
	/**
	 * 查找数组中的元素，返回下表下标
	 * @param arr  查找的数组
	 * @param value  要查找的值
	 * @return  如果返回值大于等于0，则是找的的下标，如果是-1，则没找到
	 */
	public static int searchIndex(int[] arr,int value) {
		//传统的查找方式，挨个比较
		//这种方式效率极低
		//平均查找效率为n/2
		for(int i = 0; i < arr.length; i++) {
			if(arr[i] == value) {
				return i;
			}
		}
		return -1;
	}

}
